package algorithm.dp;

// 不同路径 II
public class LC63 {
    public int uniquePathsWithObstacles(int[][] ob) {
        // 1. 定义一个 dp 表
        int m = ob.length, n = ob[0].length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        dp[1][0] = 1;
        // 3. 填表
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (ob[i-1][j-1] != 1)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
        return dp[m][n];
    }
}
